/**
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 */

// Definition for singly-linked list.
  public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

class Solution {
    public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
        if(headA == null){
            return headA;
        }
        if(headB == null){
            return headB;
        }
        ListNode temp = new ListNode();
        ListNode ret = temp;
        while(headA != null && headB != null){
            if(headA.val < headB.val){
                temp.next = headA;
                temp = temp.next;
                headA = headA.next;
            }else{
                temp.next = headB;
                temp = temp.next;
                headB = headB.next;
            }
        }
        if(headA == null){
            temp.next = headB;
        }
        if(headB == null){
            temp.next = headA;
        }
        return ret.next;
    }
}